package com.yitiao.data_algorithms.leetcode.editor.cn;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

class SquaresOfASortedArray{
    // 2022-08-23 17:43:31
    public static void main(String[] args) {
        Solution solution = new SquaresOfASortedArray().new Solution();

        solution.sortedSquares(new int[]{-4,-1,0,3,10});
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] sortedSquares(int[] nums) {
        int line = -1;
        for (int i = 0; i <nums.length ; i++) {
            if (nums[i]<0){
                line = i;
            }else
                break;
        }
        // 归并排序 相当于 合并有序数组
        int[] ans = new int[nums.length];
        int index = 0;
        int first1 = line,first2 = line + 1;
        while (first1>=0||first2< nums.length){
            if (first1<0){
                ans[index] = nums[first2] * nums[first2];
                first2++;
            }else if (first2>=nums.length){
                ans[index] = nums[first1] * nums[first1];
                first1--;
            }else
            if (nums[first1] * nums[first1]>nums[first2] * nums[first2]){
                ans[index] = nums[first2] * nums[first2];
                first2++;
            }else {
                ans[index] = nums[first1] * nums[first1];
                first1--;
            }

            index++;

        }
        return ans;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}